package org.gjy.m8.bucket;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Sliding‑Window Counter（时间戳队列）实现
 * <p>
 * 3.1 思路（时间戳列表）
 * 为每个 key 保存 最近的请求时间戳（Deque<Long>）。
 * 每次请求：
 * 移除 队列头部所有 过期（now - windowMs 之前的时间）。
 * 若 剩余数量 < limit → 加入当前时间戳 并通过；否则拒绝。
 *
 * @author gjy
 * @version 1.0
 * @since 2025-10-13 17:55:26
 */
public class SlidingWindowRateLimiter<K> implements RateLimiter<K> {

    /**
     * 每个 key 对应的时间戳双端队列（时间升序）
     */
    private static class Window {
        final long limit;
        final long windowMs;
        final Deque<Long> timestamps = new ArrayDeque<>();
        final ReentrantLock lock = new ReentrantLock(); // 细粒度锁

        Window(long limit, long windowMs) {
            this.limit = limit;
            this.windowMs = windowMs;
        }
    }

    private final ConcurrentMap<K, Window> windows;
    private final long limit;
    private final long windowMs;

    public SlidingWindowRateLimiter(long limit, long windowMs) {
        this(limit, windowMs, new ConcurrentHashMap<>());
    }

    private SlidingWindowRateLimiter(long limit, long windowMs, ConcurrentMap<K, Window> map) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.windows = map;
    }

    @Override
    public boolean tryAcquire(K key) {
        long now = System.currentTimeMillis();
        Window w = windows.computeIfAbsent(key, k -> new Window(limit, windowMs));

        w.lock.lock();
        try {
            // ① 删除已经过期的时间戳
            while (!w.timestamps.isEmpty() && now - w.timestamps.peekFirst() >= w.windowMs) {
                w.timestamps.pollFirst();
            }
            // ② 判断是否还有配额
            if (w.timestamps.size() >= w.limit) {
                return false; // 已达到窗口内上限
            }
            // ③ 加入当前时间戳并放行
            w.timestamps.offerLast(now);
            return true;
        } finally {
            w.lock.unlock();
        }
    }
}
